Many systems, including computers, network devices, storage devices, and handheld devices such as PDAs and cell phones, employ multiple subsystems, devices, and memories. These subsystems, devices, and memories are interconnected by one or more system busses over which they communicate. In some cases, a dependent multi-stage system has request may be required to service a transaction for a particular device in the system. For example, in devices employing memory management units (MMU), virtual addressing is used by the device so that it can operate from its own apparent contiguous address space. A virtual to physical address translation is performed by the MMU for each request to be sent onto the system bus so that the request is issued to the actual physical address of a memory or other device in the system. A translation look-aside buffer (TLB) is often implemented in an MMU as a cache of virtual to physical memory translations. When a request is issued with a virtual address, if the physical address associated with the virtual address is present in the TLB, then the request can be immediately issued, by the MMU to the physical address for which it is destined. A single system bus request issues in order to service the device request, thus this is a single stage request. If however the physical address associated with the virtual address is not present in the TLB, then a separate request must be issued to the system bus to retrieve the physical address from one or more page tables, usually stored in main memory. When the physical address has been retrieved, then the request itself can be issued to the system bus by the MMU. This is thus a multi-stage request requiring two system bus requests—one to retrieve a physical address, and the next to service the actual device request. The request is a dependent multi-stage request because the second stage request cannot issue until the first stage request, is completed. Therefore, this device request and all subsequent requests from the device are delayed by the latency of the first stage of the multi-stage request.
The latency associated with dependent multi-stage requests can contribute to significant performance degradation. It is desirable to service multi-stage requests in such a way as to reduce performance degradation due to the latency associated with, completing the multiple stages.